package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/5/30 14:42
 */
public class C76 {

    // 找到s中包含t的最短子串
    // 右边扩, 1) 扩到包含t的所有字符 2) 继续扩
    // 左边扩, 1) 寻找最短 2) 扩不动了右边动
    public static String minWindow(String s, String t) {
        char[] str1 = s.toCharArray(), str2 = t.toCharArray();
        int sLen = str1.length, tLen = str2.length;
        int distance = 0;   // 这个值代表, 当前窗口和t串的差距.
        int start = -1, len = Integer.MAX_VALUE;

        int l = 0, r = 0;
        int[] find = new int[58];
        int[] need = new int[58];
        for (char c : str2)
            need[c - 65]++;
        int index;
        while (r < sLen) {
            index = str1[r] - 65;
            if (find[index]++ < need[index]) {   // 如果找到了一个有效字符
                distance++;
            }
            if (distance == tLen) {  // 当前窗口l~r 包含了所有t串
                while (l <= r) {    // 缩小左边界, 找到最小子串
                    index = str1[l] - 65;
                    l++;
                    if (--find[index] < need[index]) {  // 有效字符少了就退出, 无效字符因为加入过也不会小于0的
                        distance--;
                        break;
                    }
                }
                if (r - l + 2 < len) {   // 出来的时候l多+了1
                    start = l - 1;
                    len = r - l + 2;
                }
            }
            r++;
        }
        return start == -1 ? "" : s.substring(start, start + len);
    }

    // for test
    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow(s, t));
    }

}
